9018. n-ое число, делящееся на a или b
Даны два числа a и b. Найдите n-ое
число, которое делится либо на a,
либо на b.
Вход. Три
натуральных числа a, b и n (a, b, n ≤ 109).
Выход. Выведите n-ое число, которое делится либо
на a, либо на b. Известно, что оно не более 109.
|
Пример
входа 1 |
Пример
выхода 1 |
|
2 5 10 |
16 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
3 7 25 |
57 |
РЕШЕНИЕ
бинарный
поиск
Анализ алгоритма
Пусть функция f(n) вычисляет количество натуральных чисел на промежутке [1;
n], делящихся или
на a, или на b. Это количество равно
n / a + n / b – n
/ НОК(a,
b)
Пусть x – искомое n-ое число.
Тогда x должно быть таким наименьшим
натуральным числом, что f(x) = n. Его будем искать бинарным
поиском, начиная с отрезка [left; right] = [1; 109]. Пусть mid = (left + right) / 2. Если f(mid)
≥ n, то поиск следует продолжать на отрезке [left;
mid], иначе –
на отрезке [mid + 1; right].
Пример
Рассмотрим
первый пример, в котором a = 2, b = 5. Необходимо найти наименьшее x, для которого f(x) =
10. Вычислим некоторые значения:
·
f(15)
= 15 / 2 + 15 / 5 – 15 / 10 = 7 + 3 – 1 = 9;
·
f(16)
= 16 / 2 + 16 / 5 – 16 / 10 = 8 + 3 – 1 = 10;
·
f(17)
= 17 / 2 + 17 / 5 – 17 / 10 = 8 + 3 – 1 = 10;
·
f(18)
= 18 / 2 + 18 / 5 – 18 / 10 = 9 + 3 – 1 = 11;
Наименьшим решением уравнения f(x)
= 10 будет x = 16.
Реализация алгоритма
Функции вычисления НОД и НОК.
long long gcd(long long a, long long b)
{
return (b == 0) ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
return a /
gcd(a, b) * b;
}
Функция f(n) возвращает количество натуральных чисел, не больших n, делящихся или на a, или на b.
long long f(long long n)
{
return n / a
+ n / b - n / lcm(a, b);
}
Читаем входные данные.
scanf("%lld %lld %lld",
&a, &b, &n);
Запускаем бинарный поиск. Ищем
наименьшее значение left, для которого f(left)
= n.
left = 1; right = 1e9;
while (left < right)
{
middle
= (left + right) / 2;
if
(f(middle) >= n)
right
= middle;
else
left
= middle + 1;
}
Выводим ответ.
printf("%lld\n",
left);
Java реализация
import java.util.*;
import java.io.*;
public class Main
{
static long gcd(long a, long b)
{
return (b ==
0) ? a : gcd(b, a % b);
}
static long lcm(long a, long b)
{
return a / gcd(a, b) * b;
}
static long f(long n, long a, long b)
{
return n / a + n / b - n / lcm(a, b);
}
public static void
main(String[] args)
{
FastScanner con = new
FastScanner(new InputStreamReader(System.in));
long a = con.nextInt();
long b = con.nextInt();
long n = con.nextInt();
long left = 1,
right = 1000000000;
while (left <
right)
{
long middle = (left + right) /
2;
if (f(middle, a, b)
>= n)
right = middle;
else
left = middle + 1;
}
System.out.println(left);
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public
String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch
(Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public void
close() throws Exception
{
br.close();
}
}